package com.xk._03真题骗._05动态规划;

/*
 * @description: https://leetcode.cn/problems/edit-distance/
 * @author: xu
 * @date: 2022/11/3 12:30
 */
public class _72编辑距离 {
    // 动态规划 -- 二维数组
    public int minDistance1(String word1, String word2) {
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        int[][] dp = new int[chars1.length + 1][chars2.length + 1];
        // 第0列
        for (int i = 1; i <= chars1.length; i++) {
            dp[i][0] = i;
        }
        // 第0行
        for (int j = 1; j <= chars2.length; j++) {
            dp[0][j] = j;
        }
        // 其他行 其他列
        for (int i = 1; i <= chars1.length; i++) {
            for (int j = 1; j <= chars2.length; j++) {
                int temp1 = Math.min(dp[i-1][j], dp[i][j-1]) + 1;
                int temp2 = dp[i-1][j-1];
                if (chars1[i-1] != chars2[j-1]) temp2 += 1;
                dp[i][j] = Math.min(temp1, temp2);
            }
        }
        return dp[chars1.length][chars2.length];
    }

    // 动态规划 -- 一维数组优化
    public int minDistance(String word1, String word2) {
        if (word1.length() == 0) return word2.length();
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        int[] dp = new int[chars2.length + 1];
        for (int j = 1; j <= chars2.length; j++) {
            dp[j] = j;
        }
        for (int i = 1; i <= chars1.length; i++) {
            int cur = dp[0];
            dp[0] = i;
            for (int j = 1; j <= chars2.length; j++) {
                int leftTop = cur;
                cur = dp[j];
                int temp1 = Math.min(dp[j], dp[j-1]) + 1;
                int temp2 = leftTop;
                if (chars1[i-1] != chars2[j-1]) temp2 += 1;
                dp[j] = Math.min(temp1, temp2);
            }
        }
        return dp[chars2.length];
    }

    public static void main(String[] args) {
        new _72编辑距离().minDistance("sea", "ate");
    }
}
